{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第2关：信息熵与信息增益\n",
    "\n",
    "[理论介绍](https://www.educoder.net/tasks/yjp86v29gl5n?subject_id=cuhv94tf)\n",
    "\n",
    "信息熵\n",
    "\n",
    "$$\n",
    "H(X)=−\\sum_{i=1}^{n}p(x_i)log_2(p(x_i))\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "\n",
    "def calcInfoGain(feature, label, index):\n",
    "    '''\n",
    "    计算信息增益\n",
    "    :param feature:测试用例中字典里的feature，类型为ndarray\n",
    "    :param label:测试用例中字典里的label，类型为ndarray\n",
    "    :param index:测试用例中字典里的index，即feature部分特征列的索引。该索引指的是feature中第几个特征，如index:0表示使用第一个特征来计算信息增益。\n",
    "    :return:信息增益，类型float\n",
    "    '''\n",
    "\n",
    "    #*********** Begin ***********#\n",
    "    # 标签为0的个数\n",
    "    n = len(feature)\n",
    "    n1 = np.sum(label)\n",
    "    n0 = n - n1\n",
    "    HX0 = - (n0/n * np.log2(n0/n)) - (n1/n * np.log2(n1/n))\n",
    "\n",
    "    k = list(set(feature[:, index]))\n",
    "    # print(k)\n",
    "    pi = np.zeros(shape=(len(k), 1))\n",
    "    hxi = np.zeros(shape=(len(k), 1))\n",
    "    for i, t in enumerate(k):\n",
    "        # 标签为t的样本的个数为m\n",
    "        m = np.sum(feature[:, index] == t)\n",
    "        # 在标签为t的前提下，计算样本标签为1的个数\n",
    "        m1 = np.sum(label[np.where(feature[:, index] == t)])\n",
    "        m0 = m - m1\n",
    "\n",
    "        pi[i] = m/n\n",
    "\n",
    "        if m1 == 0 or m0 == 0:\n",
    "            hxi[i] = 0\n",
    "            continue\n",
    "\n",
    "\n",
    "        # 计算hxi\n",
    "        hxi[i] = - (m0/m * np.log2(m0/m)) - (m1/m * np.log2(m1/m))\n",
    "\n",
    "    delta_H = HX0 - np.sum(pi*hxi)\n",
    "    return delta_H\n",
    "    #*********** End *************#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "feature = np.array([[0, 1], [1, 0], [1, 2], [0, 0], [1, 1]])\n",
    "label = np.array([0, 1, 0, 0, 1])\n",
    "index = 0\n",
    "feature, label, index\n",
    "calcInfoGain(feature, label, index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第3关：使用ID3算法构建决策树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "class DecisionTree(object):\n",
    "    def __init__(self):\n",
    "        #决策树模型\n",
    "        self.tree = {}\n",
    "    def calcInfoGain(self, feature, label, index):\n",
    "        '''\n",
    "        计算信息增益\n",
    "        :param feature:测试用例中字典里的feature，类型为ndarray\n",
    "        :param label:测试用例中字典里的label，类型为ndarray\n",
    "        :param index:测试用例中字典里的index，即feature部分特征列的索引。该索引指的是feature中第几个特征，如index:0表示使用第一个特征来计算信息增益。\n",
    "        :return:信息增益，类型float\n",
    "        '''\n",
    "        # 计算熵\n",
    "        def calcInfoEntropy(label):\n",
    "            '''\n",
    "            计算信息熵\n",
    "            :param label:数据集中的标签，类型为ndarray\n",
    "            :return:信息熵，类型float\n",
    "            '''\n",
    "            label_set = set(label)\n",
    "            result = 0\n",
    "            for l in label_set:\n",
    "                count = 0\n",
    "                for j in range(len(label)):\n",
    "                    if label[j] == l:\n",
    "                        count += 1\n",
    "                # 计算标签在数据集中出现的概率\n",
    "                p = count / len(label)\n",
    "                # 计算熵\n",
    "                result -= p * np.log2(p)\n",
    "            return result\n",
    "        # 计算条件熵\n",
    "        def calcHDA(feature, label, index, value):\n",
    "            '''\n",
    "            计算信息熵\n",
    "            :param feature:数据集中的特征，类型为ndarray\n",
    "            :param label:数据集中的标签，类型为ndarray\n",
    "            :param index:需要使用的特征列索引，类型为int\n",
    "            :param value:index所表示的特征列中需要考察的特征值，类型为int\n",
    "            :return:信息熵，类型float\n",
    "            '''\n",
    "            count = 0\n",
    "            # sub_feature和sub_label表示根据特征列和特征值分割出的子数据集中的特征和标签\n",
    "            sub_feature = []\n",
    "            sub_label = []\n",
    "            for i in range(len(feature)):\n",
    "                if feature[i][index] == value:\n",
    "                    count += 1\n",
    "                    sub_feature.append(feature[i])\n",
    "                    sub_label.append(label[i])\n",
    "            pHA = count / len(feature)\n",
    "            e = calcInfoEntropy(sub_label)\n",
    "            return pHA * e\n",
    "        base_e = calcInfoEntropy(label)\n",
    "        f = np.array(feature)\n",
    "        # 得到指定特征列的值的集合\n",
    "        f_set = set(f[:, index])\n",
    "        sum_HDA = 0\n",
    "        # 计算条件熵\n",
    "        for value in f_set:\n",
    "            sum_HDA += calcHDA(feature, label, index, value)\n",
    "        # 计算信息增益\n",
    "        return base_e - sum_HDA\n",
    "    # 获得信息增益最高的特征\n",
    "    def getBestFeature(self, feature, label):\n",
    "        max_infogain = 0\n",
    "        best_feature = 0\n",
    "        for i in range(len(feature[0])):\n",
    "            infogain = self.calcInfoGain(feature, label, i)\n",
    "            if infogain > max_infogain:\n",
    "                max_infogain = infogain\n",
    "                best_feature = i\n",
    "        return best_feature\n",
    "    def createTree(self, feature, label):\n",
    "        # 样本里都是同一个label没必要继续分叉了\n",
    "        if len(set(label)) == 1:\n",
    "            return label[0]\n",
    "        # 样本中只有一个特征或者所有样本的特征都一样的话就看哪个label的票数高\n",
    "        if len(feature[0]) == 1 or len(np.unique(feature, axis=0)) == 1:\n",
    "            vote = {}\n",
    "            for l in label:\n",
    "                if l in vote.keys():\n",
    "                    vote[l] += 1\n",
    "                else:\n",
    "                    vote[l] = 1\n",
    "            max_count = 0\n",
    "            vote_label = None\n",
    "            for k, v in vote.items():\n",
    "                if v > max_count:\n",
    "                    max_count = v\n",
    "                    vote_label = k\n",
    "            return vote_label\n",
    "        # 根据信息增益拿到特征的索引\n",
    "        best_feature = self.getBestFeature(feature, label)\n",
    "        tree = {best_feature: {}}\n",
    "        f = np.array(feature)\n",
    "        # 拿到bestfeature的所有特征值\n",
    "        f_set = set(f[:, best_feature])\n",
    "        # 构建对应特征值的子样本集sub_feature, sub_label\n",
    "        for v in f_set:\n",
    "            sub_feature = []\n",
    "            sub_label = []\n",
    "            for i in range(len(feature)):\n",
    "                if feature[i][best_feature] == v:\n",
    "                    sub_feature.append(feature[i])\n",
    "                    sub_label.append(label[i])\n",
    "            # 递归构建决策树\n",
    "            tree[best_feature][v] = self.createTree(sub_feature, sub_label)\n",
    "        return tree\n",
    "    def fit(self, feature, label):\n",
    "        '''\n",
    "        :param feature: 训练集数据，类型为ndarray\n",
    "        :param label:训练集标签，类型为ndarray\n",
    "        :return: None\n",
    "        '''\n",
    "        #************* Begin ************#\n",
    "        self.tree = self.createTree(feature, label)\n",
    "        #************* End **************#\n",
    "    def predict(self, feature):\n",
    "        '''\n",
    "        :param feature:测试集数据，类型为ndarray\n",
    "        :return:预测结果，如np.array([0, 1, 2, 2, 1, 0])\n",
    "        '''\n",
    "        #************* Begin ************#\n",
    "        result = []\n",
    "        def classify(tree, feature):\n",
    "            if not isinstance(tree, dict):\n",
    "                return tree\n",
    "            t_index, t_value = list(tree.items())[0]\n",
    "            f_value = feature[t_index]\n",
    "            if isinstance(t_value, dict):\n",
    "                classLabel = classify(tree[t_index][f_value], feature)\n",
    "                return classLabel\n",
    "            else:\n",
    "                return t_value\n",
    "        for f in feature:\n",
    "            result.append(classify(self.tree, f))\n",
    "        return np.array(result)\n",
    "        #************* End **************#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 草稿"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([(2,\n",
       "   {1: 0,\n",
       "    3: 1,\n",
       "    4: {0: {4: 2, 5: {3: {1: 1, 2: 2}}, 6: {1: {2: 1, 3: 1}}, 7: 1}},\n",
       "    5: {1: {2: {0: {5: 2, 6: 2}}, 3: 2}},\n",
       "    6: 2})],\n",
       " 2,\n",
       " {1: 0,\n",
       "  3: 1,\n",
       "  4: {0: {4: 2, 5: {3: {1: 1, 2: 2}}, 6: {1: {2: 1, 3: 1}}, 7: 1}},\n",
       "  5: {1: {2: {0: {5: 2, 6: 2}}, 3: 2}},\n",
       "  6: 2})"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = {2: {1: 0, 3: 1, 4: {0: {4: 2, 5: {3: {1: 1, 2: 2}}, 6: {1: {2: 1, 3: 1}}, 7: 1}}, 5: {1: {2: {0: {5: 2, 6: 2}}, 3: 2}}, 6: 2}}\n",
    "# type(tree[2][4]) == int\n",
    "t_index, t_value = list(tree.items())[0]\n",
    "list(tree.items()), t_index, t_value\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第4关：信息增益率\n",
    "\n",
    "由于在使用信息增益这一指标进行划分时，更喜欢可取值数量较多的特征。为了减少这种偏好可能带来的不利影响，Ross Quinlan使用了信息增益率这一指标来选择最优划分属性。\n",
    "\n",
    "信息增益率的数学定义为如下，其中 $D$ 表示数据集，$a$ 表示数据集中的某一列，$Gain(D,a)$ 表示 $D$ 中 $a$ 的信息增益，$V$ 表示$a$ 这一列中取值的集合，$v$ 表示$V$ 中的某种取值，$∣D∣$ 表示$D$ 中样本的数量，$∣D^v∣$ 表示 $D$ 中 $a$ 这一列中值等于 $v$ 的数量。\n",
    "\n",
    "$$\n",
    "Gain\\_ration(D,a)=\\frac{Gain(D,a)}{-\\sum_{v=1}^{V}\\frac{|D^v|}{|D|}log_2\\frac{|D^v|}{|D|}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def calcInfoGain(feature, label, index):\n",
    "    '''\n",
    "    计算信息增益\n",
    "    :param feature:测试用例中字典里的feature，类型为ndarray\n",
    "    :param label:测试用例中字典里的label，类型为ndarray\n",
    "    :param index:测试用例中字典里的index，即feature部分特征列的索引。该索引指的是feature中第几个特征，如index:0表示使用第一个特征来计算信息增益。\n",
    "    :return:信息增益，类型float\n",
    "    '''\n",
    "    # 计算熵\n",
    "    def calcInfoEntropy(label):\n",
    "        '''\n",
    "        计算信息熵\n",
    "        :param label:数据集中的标签，类型为ndarray\n",
    "        :return:信息熵，类型float\n",
    "        '''\n",
    "\n",
    "        label_set = set(label)\n",
    "        result = 0\n",
    "        for l in label_set:\n",
    "            count = 0\n",
    "            for j in range(len(label)):\n",
    "                if label[j] == l:\n",
    "                    count += 1\n",
    "            # 计算标签在数据集中出现的概率\n",
    "            p = count / len(label)\n",
    "            # 计算熵\n",
    "            result -= p * np.log2(p)\n",
    "        return result\n",
    "\n",
    "    # 计算条件熵\n",
    "    def calcHDA(feature, label, index, value):\n",
    "        '''\n",
    "        计算信息熵\n",
    "        :param feature:数据集中的特征，类型为ndarray\n",
    "        :param label:数据集中的标签，类型为ndarray\n",
    "        :param index:需要使用的特征列索引，类型为int\n",
    "        :param value:index所表示的特征列中需要考察的特征值，类型为int\n",
    "        :return:信息熵，类型float\n",
    "        '''\n",
    "        count = 0\n",
    "        # sub_label表示根据特征列和特征值分割出的子数据集中的标签\n",
    "        sub_label = []\n",
    "        for i in range(len(feature)):\n",
    "            if feature[i][index] == value:\n",
    "                count += 1\n",
    "                sub_label.append(label[i])\n",
    "        pHA = count / len(feature)\n",
    "        e = calcInfoEntropy(sub_label)\n",
    "        return pHA * e\n",
    "\n",
    "    base_e = calcInfoEntropy(label)\n",
    "    f = np.array(feature)\n",
    "    # 得到指定特征列的值的集合\n",
    "    f_set = set(f[:, index])\n",
    "    sum_HDA = 0\n",
    "    # 计算条件熵\n",
    "    for value in f_set:\n",
    "        sum_HDA += calcHDA(feature, label, index, value)\n",
    "    # 计算信息增益\n",
    "    return base_e - sum_HDA\n",
    "\n",
    "\n",
    "def calcInfoGainRatio(feature, label, index):\n",
    "    '''\n",
    "    计算信息增益率\n",
    "    :param feature:测试用例中字典里的feature，类型为ndarray\n",
    "    :param label:测试用例中字典里的label，类型为ndarray\n",
    "    :param index:测试用例中字典里的index，即feature部分特征列的索引。该索引指的是feature中第几个特征，如index:0表示使用第一个特征来计算信息增益。\n",
    "    :return:信息增益率，类型float\n",
    "    '''\n",
    "\n",
    "    #********* Begin *********#\n",
    "    fenzi = calcInfoGain(feature=feature, label=label, index=index)\n",
    "    fenmu = 0\n",
    "    D = feature.shape[0]\n",
    "    V = list(set(feature[:, index])) # feature中index这一列所有可能的取值\n",
    "    for v in V:\n",
    "        D_v = np.where(feature[:, index] == v, 1, 0).sum()\n",
    "        p = D_v / D\n",
    "        fenmu -= p*np.log2(p)\n",
    "\n",
    "    return fenzi /fenmu\n",
    "    #********* End *********#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第5关：基尼系数\n",
    "\n",
    "在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在C4.5算法中，采用了信息增益率来选择特征，以减少信息增益容易选择特征值多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的，这里面会涉及大量的**对数运算**。能不能简化模型同时也不至于完全丢失熵模型的优点呢？当然有！那就是基尼系数！\n",
    "\n",
    "CART算法使用基尼系数来代替信息增益率，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益与信息增益率是相反的(它们都是越大越好)。\n",
    "\n",
    "基尼系数的数学定义为如下，其中D表示数据集，$p_k$ 表示D中第k个类别在D中所占比例。\n",
    "\n",
    "$$\n",
    "Gini(D) = 1- \\sum_{k=1}^{|y|}{p_k}^2\n",
    "$$\n",
    "\n",
    "上面是基于数据集D的基尼系数的计算方法，那么基于数据集D与特征a的基尼系数怎样计算呢？其实和信息增益率的套路差不多。计算公式如下：\n",
    "\n",
    "$$\n",
    "Gini(D,a) = \\sum_{v=1}^{|V|}\\frac{|D^v|}{|D|}Gini(D^v)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def calcGini(feature, label, index):\n",
    "    '''\n",
    "    计算基尼系数\n",
    "    :param feature:测试用例中字典里的feature，类型为ndarray\n",
    "    :param label:测试用例中字典里的label，类型为ndarray\n",
    "    :param index:测试用例中字典里的index，即feature部分特征列的索引。该索引指的是feature中第几个特征，如index:0表示使用第一个特征来计算信息增益。\n",
    "    :return:基尼系数，类型float\n",
    "    '''\n",
    "\n",
    "    #********* Begin *********#\n",
    "\n",
    "    def calGini_(label):\n",
    "        m = len(label)\n",
    "        value = list(set(label))\n",
    "        Gini_D = 1\n",
    "        for v in value:\n",
    "            p_k = np.where(label == v, 1, 0).sum() / m\n",
    "            Gini_D -= p_k**2\n",
    "        return Gini_D\n",
    "    \n",
    "    value = list(set(feature[:, index]))\n",
    "    m = len(label)\n",
    "    Gini = 0\n",
    "    for v in value:\n",
    "        n = np.where(feature[:, index] == v, 1, 0).sum()\n",
    "        Gini_Dv = calGini_(label=label[np.where(feature[:, index] == v)])\n",
    "        Gini += n/m*Gini_Dv\n",
    "\n",
    "    return Gini\n",
    "\n",
    "    #********* End *********#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第6关：预剪枝与后剪枝\n",
    "\n",
    "**预剪枝**\n",
    "\n",
    "预剪枝的核心思想是在决策树生成过程中，对每个结点在划分前先进行一个评估，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。\n",
    "\n",
    "想要评估决策树算法的泛化性能如何，方法很简单。可以将训练数据集中随机取出一部分作为验证数据集，然后在用训练数据集对每个结点进行划分之前用当前状态的决策树计算出在验证数据集上的正确率。正确率越高说明决策树的泛化性能越好，如果在划分结点的时候发现泛化性能有所下降或者没有提升时，说明应该停止划分，并用投票计数的方式将当前结点标记成叶子结点。\n",
    "\n",
    "**后剪枝**\n",
    "\n",
    "后剪枝是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能够带来决策树泛化性能提升，则将该子树替换为叶结点。\n",
    "\n",
    "后剪枝的思路很直接，对于决策树中的每一个非叶子结点的子树，我们尝试着把它替换成一个叶子结点，该叶子结点的类别我们用子树所覆盖训练样本中存在最多的那个类来代替，这样就产生了一个简化决策树，然后比较这两个决策树在测试数据集中的表现，如果简化决策树在验证数据集中的准确率有所提高，那么该子树就可以替换成叶子结点。该算法以bottom-up的方式遍历所有的子树，直至没有任何子树可以替换使得测试数据集的表现得以改进时，算法就可以终止。\n",
    "\n",
    "从后剪枝的流程可以看出，后剪枝是从全局的角度来看待要不要剪枝，所以造成欠拟合现象的可能性比较小。但由于后剪枝需要先生成完整的决策树，然后再剪枝，所以后剪枝的训练时间开销更高。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from copy import deepcopy\n",
    "class DecisionTree(object):\n",
    "    def __init__(self):\n",
    "        #决策树模型\n",
    "        self.tree = {}\n",
    "    def calcInfoGain(self, feature, label, index):\n",
    "        '''\n",
    "        计算信息增益\n",
    "        :param feature:测试用例中字典里的feature，类型为ndarray\n",
    "        :param label:测试用例中字典里的label，类型为ndarray\n",
    "        :param index:测试用例中字典里的index，即feature部分特征列的索引。该索引指的是feature中第几个特征，如index:0表示使用第一个特征来计算信息增益。\n",
    "        :return:信息增益，类型float\n",
    "        '''\n",
    "        # 计算熵\n",
    "        def calcInfoEntropy(feature, label):\n",
    "            '''\n",
    "            计算信息熵\n",
    "            :param feature:数据集中的特征，类型为ndarray\n",
    "            :param label:数据集中的标签，类型为ndarray\n",
    "            :return:信息熵，类型float\n",
    "            '''\n",
    "            label_set = set(label)\n",
    "            result = 0\n",
    "            for l in label_set:\n",
    "                count = 0\n",
    "                for j in range(len(label)):\n",
    "                    if label[j] == l:\n",
    "                        count += 1\n",
    "                # 计算标签在数据集中出现的概率\n",
    "                p = count / len(label)\n",
    "                # 计算熵\n",
    "                result -= p * np.log2(p)\n",
    "            return result\n",
    "        # 计算条件熵\n",
    "        def calcHDA(feature, label, index, value):\n",
    "            '''\n",
    "            计算信息熵\n",
    "            :param feature:数据集中的特征，类型为ndarray\n",
    "            :param label:数据集中的标签，类型为ndarray\n",
    "            :param index:需要使用的特征列索引，类型为int\n",
    "            :param value:index所表示的特征列中需要考察的特征值，类型为int\n",
    "            :return:信息熵，类型float\n",
    "            '''\n",
    "            count = 0\n",
    "            # sub_feature和sub_label表示根据特征列和特征值分割出的子数据集中的特征和标签\n",
    "            sub_feature = []\n",
    "            sub_label = []\n",
    "            for i in range(len(feature)):\n",
    "                if feature[i][index] == value:\n",
    "                    count += 1\n",
    "                    sub_feature.append(feature[i])\n",
    "                    sub_label.append(label[i])\n",
    "            pHA = count / len(feature)\n",
    "            e = calcInfoEntropy(sub_feature, sub_label)\n",
    "            return pHA * e\n",
    "        base_e = calcInfoEntropy(feature, label)\n",
    "        f = np.array(feature)\n",
    "        # 得到指定特征列的值的集合\n",
    "        f_set = set(f[:, index])\n",
    "        sum_HDA = 0\n",
    "        # 计算条件熵\n",
    "        for value in f_set:\n",
    "            sum_HDA += calcHDA(feature, label, index, value)\n",
    "        # 计算信息增益\n",
    "        return base_e - sum_HDA\n",
    "    # 获得信息增益最高的特征\n",
    "    def getBestFeature(self, feature, label):\n",
    "        max_infogain = 0\n",
    "        best_feature = 0\n",
    "        for i in range(len(feature[0])):\n",
    "            infogain = self.calcInfoGain(feature, label, i)\n",
    "            if infogain > max_infogain:\n",
    "                max_infogain = infogain\n",
    "                best_feature = i\n",
    "        return best_feature\n",
    "    # 计算验证集准确率\n",
    "    def calc_acc_val(self, the_tree, val_feature, val_label):\n",
    "        result = []\n",
    "        def classify(tree, feature):\n",
    "            if not isinstance(tree, dict):\n",
    "                return tree\n",
    "            t_index, t_value = list(tree.items())[0]\n",
    "            f_value = feature[t_index]\n",
    "            if isinstance(t_value, dict):\n",
    "                classLabel = classify(tree[t_index][f_value], feature)\n",
    "                return classLabel\n",
    "            else:\n",
    "                return t_value\n",
    "        for f in val_feature:\n",
    "            result.append(classify(the_tree, f))\n",
    "        result = np.array(result)\n",
    "        return np.mean(result == val_label)\n",
    "    def createTree(self, train_feature, train_label):\n",
    "        # 样本里都是同一个label没必要继续分叉了\n",
    "        if len(set(train_label)) == 1:\n",
    "            return train_label[0]\n",
    "        # 样本中只有一个特征或者所有样本的特征都一样的话就看哪个label的票数高\n",
    "        if len(train_feature[0]) == 1 or len(np.unique(train_feature, axis=0)) == 1:\n",
    "            vote = {}\n",
    "            for l in train_label:\n",
    "                if l in vote.keys():\n",
    "                    vote[l] += 1\n",
    "                else:\n",
    "                    vote[l] = 1\n",
    "            max_count = 0\n",
    "            vote_label = None\n",
    "            for k, v in vote.items():\n",
    "                if v > max_count:\n",
    "                    max_count = v\n",
    "                    vote_label = k\n",
    "            return vote_label\n",
    "        # 根据信息增益拿到特征的索引\n",
    "        best_feature = self.getBestFeature(train_feature, train_label)\n",
    "        tree = {best_feature: {}}\n",
    "        f = np.array(train_feature)\n",
    "        # 拿到bestfeature的所有特征值\n",
    "        f_set = set(f[:, best_feature])\n",
    "        # 构建对应特征值的子样本集sub_feature, sub_label\n",
    "        for v in f_set:\n",
    "            sub_feature = []\n",
    "            sub_label = []\n",
    "            for i in range(len(train_feature)):\n",
    "                if train_feature[i][best_feature] == v:\n",
    "                    sub_feature.append(train_feature[i])\n",
    "                    sub_label.append(train_label[i])\n",
    "            # 递归构建决策树\n",
    "            tree[best_feature][v] = self.createTree(sub_feature, sub_label)\n",
    "        return tree\n",
    "    # 后剪枝\n",
    "    def post_cut(self, val_feature, val_label):\n",
    "        # 拿到非叶子节点的数量\n",
    "        def get_non_leaf_node_count(tree):\n",
    "            non_leaf_node_path = []\n",
    "            def dfs(tree, path, all_path):\n",
    "                for k in tree.keys():\n",
    "                    if isinstance(tree[k], dict):\n",
    "                        path.append(k)\n",
    "                        dfs(tree[k], path, all_path)\n",
    "                        if len(path) > 0:\n",
    "                            path.pop()\n",
    "                    else:\n",
    "                        all_path.append(path[:])\n",
    "            dfs(tree, [], non_leaf_node_path)\n",
    "            unique_non_leaf_node = []\n",
    "            for path in non_leaf_node_path:\n",
    "                isFind = False\n",
    "                for p in unique_non_leaf_node:\n",
    "                    if path == p:\n",
    "                        isFind = True\n",
    "                        break\n",
    "                if not isFind:\n",
    "                    unique_non_leaf_node.append(path)\n",
    "            return len(unique_non_leaf_node)\n",
    "        # 拿到树中深度最深的从根节点到非叶子节点的路径\n",
    "        def get_the_most_deep_path(tree):\n",
    "            non_leaf_node_path = []\n",
    "            def dfs(tree, path, all_path):\n",
    "                for k in tree.keys():\n",
    "                    if isinstance(tree[k], dict):\n",
    "                        path.append(k)\n",
    "                        dfs(tree[k], path, all_path)\n",
    "                        if len(path) > 0:\n",
    "                            path.pop()\n",
    "                    else:\n",
    "                        all_path.append(path[:])\n",
    "            dfs(tree, [], non_leaf_node_path)\n",
    "            max_depth = 0\n",
    "            result = None\n",
    "            for path in non_leaf_node_path:\n",
    "                if len(path) > max_depth:\n",
    "                    max_depth = len(path)\n",
    "                    result = path\n",
    "            return result\n",
    "        # 剪枝\n",
    "        def set_vote_label(tree, path, label):\n",
    "            for i in range(len(path)-1):\n",
    "                tree = tree[path[i]]\n",
    "            tree[path[len(path)-1]] = vote_label\n",
    "        acc_before_cut = self.calc_acc_val(self.tree, val_feature, val_label)\n",
    "        # 遍历所有非叶子节点\n",
    "        for _ in range(get_non_leaf_node_count(self.tree)):\n",
    "            path = get_the_most_deep_path(self.tree)\n",
    "            # 备份树\n",
    "            tree = deepcopy(self.tree)\n",
    "            step = deepcopy(tree)\n",
    "            # 跟着路径走\n",
    "            for k in path:\n",
    "                step = step[k]\n",
    "            # 叶子节点中票数最多的标签\n",
    "            vote_label = sorted(step.items(), key=lambda item: item[1], reverse=True)[0][0]\n",
    "            # 在备份的树上剪枝\n",
    "            set_vote_label(tree, path, vote_label)\n",
    "            acc_after_cut = self.calc_acc_val(tree, val_feature, val_label)\n",
    "            # 验证集准确率高于0.9才剪枝\n",
    "            if acc_after_cut > acc_before_cut:\n",
    "                set_vote_label(self.tree, path, vote_label)\n",
    "                acc_before_cut = acc_after_cut\n",
    "    def fit(self, train_feature, train_label, val_feature, val_label):\n",
    "        '''\n",
    "        :param train_feature:训练集数据，类型为ndarray\n",
    "        :param train_label:训练集标签，类型为ndarray\n",
    "        :param val_feature:验证集数据，类型为ndarray\n",
    "        :param val_label:验证集标签，类型为ndarray\n",
    "        :return: None\n",
    "        '''\n",
    "        #************* Begin ************#\n",
    "        self.tree = self.createTree(train_feature, train_label)\n",
    "        # 后剪枝\n",
    "        self.post_cut(val_feature, val_label)\n",
    "        #************* End **************#\n",
    "    def predict(self, feature):\n",
    "        '''\n",
    "        :param feature:测试集数据，类型为ndarray\n",
    "        :return:预测结果，如np.array([0, 1, 2, 2, 1, 0])\n",
    "        '''\n",
    "        #************* Begin ************#\n",
    "        result = []\n",
    "        def classify(tree, feature):\n",
    "            if not isinstance(tree, dict):\n",
    "                return tree\n",
    "            t_index, t_value = list(tree.items())[0]\n",
    "            f_value = feature[t_index]\n",
    "            if isinstance(t_value, dict):\n",
    "                classLabel = classify(tree[t_index][f_value], feature)\n",
    "                return classLabel\n",
    "            else:\n",
    "                return t_value\n",
    "        for f in feature:\n",
    "            result.append(classify(self.tree, f))\n",
    "        return np.array(result)\n",
    "        #************* End **************#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第七关：鸢尾花识别\n",
    "\n",
    "**DecisionTreeClassifier**\n",
    "\n",
    "`DecisionTreeClassifier` 的构造函数中有两个常用的参数可以设置：\n",
    "\n",
    "- `criterion`:划分节点时用到的指标。有 `gini`（基尼系数）, `entropy`(信息增益)。若不设置，默认为 `gini`\n",
    "- `max_depth`:决策树的最大深度，如果发现模型已经出现过拟合，可以尝试将该参数调小。若不设置，默认为 `None`\n",
    "\n",
    "\n",
    "和sklearn中其他分类器一样， `DecisionTreeClassifier` 类中的 fit 函数用于训练模型，fit 函数有两个向量输入：\n",
    "\n",
    "- X：大小为[样本数量,特征数量]的ndarray，存放训练样本；\n",
    "\n",
    "- Y：值为整型，大小为[样本数量]的ndarray，存放训练样本的分类标签。\n",
    "\n",
    "DecisionTreeClassifier类中的predict函数用于预测，返回预测标签，predict函数有一个向量输入：\n",
    "\n",
    "- X：大小为[样本数量,特征数量]的ndarray，存放预测样本。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#********* Begin *********#\n",
    "import pandas as pd\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "\n",
    "# as_matrix()可以将DataFrame转换成ndarray\n",
    "# 此时train_df的类型为ndarray而不是DataFrame\n",
    "X_train = pd.read_csv('./step7/train_data.csv').as_matrix()\n",
    "Y_train = pd.read_csv('./step7/train_label.csv').as_matrix()\n",
    "X_test = pd.read_csv('./step7/test_data.csv').as_matrix()\n",
    "\n",
    "clf = DecisionTreeClassifier(criterion='entropy')\n",
    "clf.fit(X_train, Y_train)\n",
    "result = clf.predict(X_test)\n",
    "'''\n",
    "pd.DateFrame(result, colums=['target']).to_csc('./step7/predict.csv')\n",
    "会报错，不懂，很奇怪\n",
    "'''\n",
    "result = pd.DataFrame({'target':result})\n",
    "result.to_csv('./step7/predict.csv', index=False)\n",
    "#********* End *********#\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "tf38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.19"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
